Flash memory is a form of non-volatile memory (NVM) that can be electrically erased and reprogrammed (or written). Flash memory architecture allows multiple memory locations to be erased or written in one programming operation. Two common types of flash memory are NOR and NAND flash. NOR and NAND flash get their names from the structure of the interconnections between memory cells. In NOR flash, cells are connected in parallel to the bitlines, allowing cells to be read and programmed individually. The parallel connection of cells resembles the parallel connection of transistors in a CMOS NOR gate. In NAND flash, cells are connected in series, resembling a NAND gate, and preventing cells from being read and programmed individually: the cells connected in series must be read in series.
NAND Flash memory constitutes a fundamental building block in wide variety of modern electronic systems. Flash memory may comprise a large number of floating gate (FG) memory cells arranged in an array, and connected to a plurality of wordlines (WLs) and bitlines (BLs).
Memory Array Architecture, Generally
Typically, NVM memory cells are arranged in an array comprising many rows and columns, between wordlines extending horizontally (as usually depicted) across the array and bitlines extending vertically (as usually depicted) up and down the array. A memory array typically comprises many millions (“mega”), including billions (“giga”) of memory cells.
A memory array typically comprises a plurality of bitlines (BL) extending in parallel with one another vertically through the array (or a portion thereof), and a plurality of wordlines (WL) extending in parallel with one another horizontally through the array (or a portion thereof).
A plurality of memory cells may be connected between the wordlines and bitlines. Some of the memory cells may be connected to the same wordline. Some other of the memory cells may be connected to the same bitline. In a most general sense, the physical address of each cell may be specified by a combination of which wordline (WL#) and which bitline (BL#) a given memory cell is connected to. In other words, any individual one of the memory cells (mc) can be addressed by specifying a wordline and a bitline. Since only one unique memory cell is associated with a given combination of wordline/bitline, the combination of wordline number and bitline number may be considered to be the cell's “native” address.
A memory array may be organized into various logical sections containing pluralities of memory cells, such as blocks, pages and sectors. Some of these sections may be physically isolated and operated independently from one another. Some terminology which may be applied to sections of a memory array (or selected pluralities of memory cells) are:
blocks—may refer to a group of pages. May refer to the minimal number of cells (and, the corresponding number of bits) that can be erased simultaneously, in this case it is called “erase sector”. Typical size may be 64 Kbytes.
chunks—may refer to parts of page. Can be also called “hunk”. A typical chunk size may be 256 bits.
erase sectors—see “blocks”
pages—page may be the minimal number of bits on flash array that can be programmed simultaneously, or can programmed by a single user operation. The user is required to program data into the flash in chunks of entire pages. Typical page size is 2 Kbytes, 4 Kbytes.
physical sectors—a group of “erase sectors” or “blocks”. Typical size may be 256 Kbytes
slices—a group of bits on the array with a specific connection configuration to sense amplifiers.
Program Levels
Generally, the more electrons that are stored (or trapped), the higher the threshold voltage (Vt) of the cell may be. Threshold voltage refers to a voltage that is required to be applied to the gate to cause a measurable threshold level of conduction in the channel.
In single level programming (SLC), a small number of electrons may be stored to represent a first program level, such as binary “0”, and a larger number of electrons may be stored to represent a second program level such as binary “1”. In SLC, only two program levels are available, and one of these may be considered to be the “erase” state.
In multi-level programming (MLC), there may be more than two, such as four program levels (L0 . . . Ln). A lowest program level (which may be “erase”), may represent binary “11”. A next higher program level may represent binary “01”. A next higher program level may represent binary “00”. And a highest of the four program levels may represent binary “10”. (This seemingly miss-ordered sequence of 11, 01, 10, 00 is representative of “Gray Code”, which is a binary numeral system where two successive values differ in only one digit.) More than four program levels are possible—for example, 16 program levels (L=0 . . . 15; with L0 typically being an erase state.)
Reliability Issues
When storing electrons at different (such as four different) program levels in many memory cells (or half cells), there are inevitably distributions (or widths) of threshold voltages (Vt) at each of the program levels. This dictates that the levels be established sufficiently far apart from one another so that when reading the contents of the cell, there is good separation (or “margin”) between adjacent program levels.
The width of each distribution is dependent on physical phenomena. It may be determined via various experiments on the manufacturing process, observing all possible combinations of program level on various memory cells.
Various factors may affect the quality and reliability of NVM cells. For example, programming one cell may cause injection of electrons into nearby or neighboring cells, affecting (raising or lowering) their Vt. Generally, changes in the Vt of a memory cell, occurring after it has been programmed (or erased), may be referred to as “threshold voltage drift”. Threshold voltage drift is well known, and is discussed for example in U.S. Pat. Nos. 6,992,932 and 6,963,505, incorporated by reference herein.
As margins between adjacent program levels shrink, it may become increasingly difficult to accurately read the contents of the memory cell (or half cell). An extreme example would be “overlap”, where some of the highest Vt cells of one program level are at the same or higher value than some of the lowest Vt of cells at the next higher program level. “Cells” may refer to floating gate (FG) cells which have one charge storage area each, or may refer to NROM cells which have two distinct charge storage areas.
When reading an NROM cell (a single cell having two distinct charge storage areas), the Vt of the other (second) bit (or half cell) will exert an influence on the measured Vt for the bit being read, and this may be referred to as the “second bit effect”.
The “second bit effect” may also refer to situations where a low charge zone (such as “11”) is gaining charge when it is near a high charge zone (such as “10”). This definition of second bit effect will be used in the description that follows.
FIG. 1A illustrates a threshold distribution for 2 bit per cell NVM cells assuming (theoretically) that there is no inter-cell coupling and FIG. 1B illustrates the widening of the threshold distributions per program level as a result of the inter-cell coupling. The four lobes (four threshold distributions for four different program levels 11-14 of FIG. 1A are much narrower than those (15-18) of FIG. 1B.
FIG. 1C illustrates nine FG memory cells 20(1)-20(9) connected in a conventional manner to corresponding three wordlines 21(1)-21(3) and three bitlines 22(1)-22(3). A given cell (“C”) (or “cell of interest”) may be surrounded by adjacent or neighbor cells (“N”) in the horizontal direction (on the same wordline) in the vertical direction (on the same bitline) and in the diagonal direction (one wordline and one bitline distant from the given cell (“C”). This figure illustrates neighboring cells that affect inter-cell coupling in NAND Flash. The adjacent neighbor cells (with distance 1) of the cell “C” are marked Nx for x axis, Ny for y axis and Nd for diagonal.
The “problem” and “solution” described herein may be most evident in MLC cells. In multi-level programming (MLC), there may be more than two, such as four, eight, sixteen, or more program levels “L”. (The number of levels need not be an integer power of two.) These levels may be referred to simply as L0, L1, L2, L3, etc, with each level representing a nominal threshold voltage higher than the previous one (VtL0<VtL1<VtL2<VtL3, etc). (The lowest level “L0” may actually be an initial “erase” level, but may be considered to be the lowest “program” level for purposes of this discussion.
As NAND Flash memory process technology scales below 32 nm and the number of charge levels per cell exceeds eight, cell threshold voltage distributions may be narrower in order to prevent errors resulting from distribution overlap. An obstacle to achieving narrow threshold voltage distributions in floating-gate (FG) cells is the inter-cell coupling effect. This effect shifts the sensed threshold voltage of a given cell by a degree that depends on (i) the level of coupling between the given cell (“C”) and adjacent/neighboring cells (“N”) and (ii) on the amount of charge in the surrounding cells. (Particularly, whenever a cell is charged iteratively, whereby in each iteration some charge is added to it followed by a determination of its threshold voltage, and its charging terminated once the target threshold voltage has been reached, only the charge added to the neighboring cells of a given cell subsequent to the termination of its own charging should affect its threshold voltage.) Whenever the charge levels in neighboring cells or the programming order are not known or not considered, this effect may manifest itself as an apparent broadening of the threshold voltage distributions in cells which have been programmed to a nominal program level “L”.
FIG. 2 illustrates inter-cell coupling capacitance between floating gates 30(1)-30(9) of a given cell (“C”) and its neighboring cells (“Nn”). These cells can be FG cells 20(1)-20(9) of FIG. 1C.
Coupling components shown in the figure are: CFGX, CFGY, CFGXY. The component CFGCG is the capacitance between the centered floating gate to the control gate of the neighbor cell, and it is not shown in the figure. Corresponding voltages of floating gates in neighboring cells are marked V1, V2, V3 V4.
Some traditional designs handle the inter-cell coupling effect in several approaches. Adjusted cell programming algorithms program the cells to intermediate levels and sense the threshold voltage change in order to capture the coupling effect. However, those methods may result in slow programming, and since programming is done in one wordline, the programming methods do not cover the case of inter-wordline coupling and diagonal coupling.
It should be understood that before actually writing user data to an NVM memory device, the data is typically “coded” to accommodate features and characteristics of the device in which it is being stored (or medium through which it is being transmitted) Generally, coding transforms user data from a user format (may be plain data of data which was transformed by other coding system) to another data format in order to get system benefits such as compression (for example, to save power), error protection (when data may be prone to errors) or cryptography (protection of exposing the data). Coding systems are in use with memory as well as regular communication systems. The overall goal of a coding system is handling the data, and should be transparent to the user. Data compression and encryption can be included in a coding system. Coding usually adds redundancy to the data, which may be for error-checking, but it can also or alternatively be a decoding dictionary for compression or cryptography key for compression.
Coding Theory
Generally, a “coding system” is a system or algorithm which transforms user data from a user format (may be plain data of data which was transformed by other coding system) to another data format in order to get system benefits such as compression (for example, to save power), error protection (when data may be prone to errors) or cryptography (protection of exposing the data). Coding system is in use with memory as well as regular communication systems. The overall goal of a coding system is handling the data, and should be transparent to the user. Data compression and encryption can be included in a coding system. Coding usually adds redundancy to the data, which may be for error-checking, but it can also or alternatively be a decoding dictionary for compression or cryptography key for compression.
Generally, “user data” is data provided by any entity using the NVM (or flash chip). From the user's perspective, the NVM is a “black box”, the user writes information (data) into it, and expects to get the information back from it.
Coding theory is one of the most important and direct applications of information theory. It is a branch of electrical engineering, digital communication, mathematics, and computer science designing efficient and reliable data transmission methods, so that redundancy in the data can be removed and errors induced by a noisy channel can be corrected. It also deals with the properties of codes, and thus with their fitness for a specific application. There are generally three classes of codes.    1. Source coding (Data compression)    2. Channel coding (Forward error correction)    3. Joint source and channel coding
A source code is used to compress words (or phrases or data) by mapping common words into shorter words (e.g. Huffman Code). Source encoding, attempts to compress the data from a source in order to transmit it more efficiently. This practice is common on the Internet where “Zip” data compression is used to reduce the network load and make files smaller.
A channel code contains redundancy to allow more reliable communication in the presence of noise. This redundancy means that only a limited set of signals is allowed: this set is the code. Channel encoding adds extra data bits to make the transmission of data more robust to disturbances present on the transmission channel. The ordinary user may not be aware of many applications using channel coding. A typical music CD uses the Reed-Solomon code to correct for scratches and dust. In this application the transmission channel is the CD itself. Cell phones also use coding techniques to correct for the fading and noise of high frequency radio transmission. Data modems, telephone transmissions, and of course NASA all employ channel coding techniques to get the bits through, for example the turbo code and LDPC codes.
Joint source-channel coding is the encoding of a redundant information source for transmission over a noisy channel, and the corresponding decoding, using a single code instead of the more conventional steps of source coding followed by channel coding. Joint source-channel coding has been proposed and implemented for a variety of situations, including speech and video transmission.
The aim of channel coding theory is to find codes which transmit quickly, contain many valid code words and can correct or at least detect many errors. While not mutually exclusive, performance in these areas is a trade off. So, different codes are optimal for different applications. The needed properties of this code mainly depend on the probability of errors happening during transmission. In a typical CD, the impairment is mainly dust or scratches. Other codes are more appropriate for different applications. Deep space communications are limited by the thermal noise of the receiver which is more of a continuous nature than a bursty nature. Likewise, narrowband modems are limited by the noise present in the telephone network and is also modeled better as a continuous disturbance. Cell phones are subject to rapid fading. The high frequencies used can cause rapid fading of the signal even if the receiver is moved a few inches. Again there are classes of channel codes that are designed to combat fading.
The following terms may be commonly used in description of coding techniques: bit—The word “bit” is a shortening of the words “binary digit.” A bit refers to a digit in the binary numeral system (base 2). A given bit is either a binary “1” or “0”. For example, the number 1001011 is 7 bits long.
byte—A byte is commonly used as a unit of storage measurement in computers, regardless of the type of data being stored. It is also one of the basic integral data types in many programming languages. A byte is a contiguous sequence of a fixed number of binary bits. In recent years, the use of a byte to mean 8 bits is nearly ubiquitous. The unit is sometimes abbreviated to “B”. Terms for large quantities of Bytes can be formed using the standard range of prefixes, for example, kilobyte (KB), megabyte (MB) and gigabyte (GB).codebook—A codebook is simply the “instructions” on how to encode an input word to a coded word. Starting with a “word”, using a codebook, the data sequence for the word will be a “codeword” (or coded word). The codebook also contains the “instructions” on how to decode a coded word back to its original input word. The instructions may be detailed algorithms explaining the conversion or simply a look-up table having two columns: one column for input words (word—a sequence of bits) and second column for coded words where each word on the input words column is to transform to the word in the coded column (in the same row), and vice-versa.coding—The process of converting information obtained on a subject or unit into coded values (typically numeric) for the purpose of data storage, management, and analysis.    codeword—short for coded word. See codebook.    symbol—The term “symbol” may refer to a group of bits.    word—The term “word” is used on specific communication systems field and may refer to the input word (input sequence of bits) or codeword, both are groups (may be rarely of size 1 bit) of bits.
Constrained Coding
One form of coding is constraint (or constrained) coding. Constraint coding generally prescribes (and implicitly prohibits) certain data patterns to ensure compatibility with a storage medium, such as hard drive or optical disc. If a data pattern does not meet the constraints, it is deemed to be “illegal”, and a coding function may be applied to change the pattern, with added redundancy. For storage devices such as hard drive and optical disc, the physics of the storage medium generally demands that constraint coding is used. An example may be prohibiting the writing of four “1s” in a row. As used herein, “modulated coding” means the same thing as “constraint coding”. Note that even if the data is “legal”, a constraint coding system may add redundancy in order to distinguish between coded data patterns.
The following patents, directed to constrained coding, are incorporated by referenced herein:
U.S. Pat. No. 6,532,565 discloses burst error and additional random bit error correction in a memory.
U.S. Pat. No. 6,188,335 discloses method and apparatus having cascaded decoding for multiple run length-limited channel codes.
U.S. Pat. No. 6,175,317 discloses two-dimensional DC-free encoder and decoder.
U.S. Pat. No. 6,002,718, 1999, and European Patent 771,078 disclose method and apparatus for generating run length-limited coding with DC control.
U.S. Pat. No. 5,719,884 discloses error correction method and apparatus based on two-dimensional code array with reduced redundancy.
See also “An Introduction to Coding for Constrained Systems”, Brian H. Marcus, Ron M. Roth, Paul H. Siegel, fifth edition, October 2001, incorporated by reference herein.
Available online at http://www.cs.technion.ac.il/˜ronny/constrained.html and also at http://webcourse.cs.technion.ac.il/236520/Spring2010/en/ho.html